home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / TEMP / GNU / bison / Languagean < prev    next >
Text File  |  1995-06-28  |  5KB  |  104 lines
  1. Language and Grammar
  2. Previous: <Concepts=>Concepts> * Next: <Grammar in Bison=>GrammarinB> * Up: <Concepts=>Concepts>
  3.  
  4. #Wrap on
  5. {fH3}Languages and Context-Free Grammars{f}
  6.  
  7. In order for Bison to parse a language, it must be described by a
  8. {fUnderline}context-free grammar{f}.  This means that you specify one or more
  9. {fUnderline}syntactic groupings{f} and give rules for constructing them from their
  10. parts.  For example, in the C language, one kind of grouping is called an
  11. `expression'.  One rule for making an expression might be, ``An expression
  12. can be made of a minus sign and another expression''.  Another would be,
  13. ``An expression can be an integer''.  As you can see, rules are often
  14. recursive, but there must be at least one rule which leads out of the
  15. recursion.
  16.  
  17. The most common formal system for presenting such rules for humans to read
  18. is {fUnderline}Backus-Naur Form{f} or ``BNF'', which was developed in order to
  19. specify the language Algol 60.  Any grammar expressed in BNF is a
  20. context-free grammar.  The input to Bison is essentially machine-readable
  21. BNF.
  22.  
  23. Not all context-free languages can be handled by Bison, only those
  24. that are LALR(1).  In brief, this means that it must be possible to
  25. tell how to parse any portion of an input string with just a single
  26. token of look-ahead.  Strictly speaking, that is a description of an
  27. LR(1) grammar, and LALR(1) involves additional restrictions that are
  28. hard to explain simply; but it is rare in actual practice to find an
  29. LR(1) grammar that fails to be LALR(1).  \*Note <Mystery Conflicts=>MysteryCon>: Mysterious Reduce\/Reduce Conflicts, for more information on this.
  30.  
  31. In the formal grammatical rules for a language, each kind of syntactic unit
  32. or grouping is named by a {fUnderline}symbol{f}.  Those which are built by grouping
  33. smaller constructs according to grammatical rules are called
  34. {fUnderline}nonterminal symbols{f}; those which can't be subdivided are called
  35. {fUnderline}terminal symbols{f} or {fUnderline}token types{f}.  We call a piece of input
  36. corresponding to a single terminal symbol a {fUnderline}token{f}, and a piece
  37. corresponding to a single nonterminal symbol a {fUnderline}grouping{f}.
  38.  
  39. We can use the C language as an example of what symbols, terminal and
  40. nonterminal, mean.  The tokens of C are identifiers, constants (numeric and
  41. string), and the various keywords, arithmetic operators and punctuation
  42. marks.  So the terminal symbols of a grammar for C include `identifier',
  43. `number', `string', plus one symbol for each keyword, operator or
  44. punctuation mark: `if', `return', `const', `static', `int', `char',
  45. `plus-sign', `open-brace', `close-brace', `comma' and many more.  (These
  46. tokens can be subdivided into characters, but that is a matter of
  47. lexicography, not grammar.)
  48.  
  49. Here is a simple C function subdivided into tokens:
  50.  
  51. #Wrap off
  52. #fCode
  53. int             \/\* keyword `int' \*\/
  54. square (x)      \/\* identifier, open-paren, \*\/
  55.                 \/\* identifier, close-paren \*\/
  56.      int x;     \/\* keyword `int', identifier, semicolon \*\/
  57. \{               \/\* open-brace \*\/
  58.   return x \* x; \/\* keyword `return', identifier, \*\/
  59.                 \/\* asterisk, identifier, semicolon \*\/
  60. \}               \/\* close-brace \*\/
  61. #f
  62. #Wrap on
  63.  
  64. The syntactic groupings of C include the expression, the statement, the
  65. declaration, and the function definition.  These are represented in the
  66. grammar of C by nonterminal symbols `expression', `statement',
  67. `declaration' and `function definition'.  The full grammar uses dozens of
  68. additional language constructs, each with its own nonterminal symbol, in
  69. order to express the meanings of these four.  The example above is a
  70. function definition; it contains one declaration, and one statement.  In
  71. the statement, each {fEmphasis}x{f} is an expression and so is {fEmphasis}x \* x{f}.
  72.  
  73. Each nonterminal symbol must have grammatical rules showing how it is made
  74. out of simpler constructs.  For example, one kind of C statement is the
  75. {fCode}return{f} statement; this would be described with a grammar rule which
  76. reads informally as follows:
  77.  
  78. #fCite
  79. A `statement' can be made of a `return' keyword, an `expression' and a
  80. `semicolon'.
  81. #f
  82.  
  83. There would be many other rules for `statement', one for each kind of
  84. statement in C.
  85.  
  86. One nonterminal symbol must be distinguished as the special one which
  87. defines a complete utterance in the language.  It is called the {fUnderline}start
  88. symbol{f}.  In a compiler, this means a complete input program.  In the C
  89. language, the nonterminal symbol `sequence of definitions and declarations'
  90. plays this role.
  91.  
  92. For example, {fEmphasis}1 + 2{f} is a valid C expression---a valid part of a C
  93. program---but it is not valid as an {fEmphasis}entire{f} C program.  In the
  94. context-free grammar of C, this follows from the fact that `expression' is
  95. not the start symbol.
  96.  
  97. The Bison parser reads a sequence of tokens as its input, and groups the
  98. tokens using the grammar rules.  If the input is valid, the end result is
  99. that the entire token sequence reduces to a single grouping whose symbol is
  100. the grammar's start symbol.  If we use a grammar for C, the entire input
  101. must be a `sequence of definitions and declarations'.  If not, the parser
  102. reports a syntax error.
  103.  
  104.